package com.demo.java.OD1_50.OD49;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【租车骑绿岛】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145584397
 */
public class OdMain {
    private static void solveMethod(int m, int n, ArrayList<Integer> weights) {
        // 排序体重
        Collections.sort(weights);

        // 使用双指针从两端开始
        int start = 0;
        int end = weights.size() - 1;

        // 结果，表示需要的最少车数
        int minResult = 0;

        // 循环直到所有乘客都安排好
        while (start <= end) {
            // 判断当前最重和最轻的乘客能否一起乘车
            if (weights.get(start) + weights.get(end) <= m) {
                // 能一起乘车，两个指针都向中间移动
                start++;
            }
            // 最重的乘客单独乘车
            end--;
            // 每次操作都需要增加一辆车
            minResult++;
        }

        // 输出最少的车数
        System.out.println(minResult);
    }

    public static void main(String[] args) {
        try {
            Scanner s = new Scanner(System.in);
            int m = s.nextInt();  // 车的最大承载重量
            int n = s.nextInt();  // 乘客数量
            ArrayList<Integer> weights = new ArrayList<Integer>();  // 存储所有乘客的体重
            for (int i = 0; i < n; i++) {
                int a = s.nextInt();
                weights.add(a);
            }
            solveMethod(m, n, weights);  // 调用方法计算最少车数
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}